Finding the solution to a problem is typically dependent on finding a set of variable values that satisfy a set of predicates or constraints. A problem may be defined by variables X and Y such that Y=X+2. The following set of constraints defines the limitations associated with each variable: 0<X<5; Y>5. A solution to the problem within the boundaries (i.e., domains) defined by the constraints would be: X=4; Y=6, for example.
A problem such as the exemplary one provided above is commonly referred to as a constraint satisfaction problem (CSP). Many of the tasks that are addressed by decision-making systems can be framed as CSPs. In such a framework, a task is specified in terms of a problem with a set of variables (each of which can assume values within a given domain) and a set of constraints that the variables must satisfy.
Each constraint may be expressed as a relation, defined over some subset of the variables, denoting valid combinations of their values. As provided in the above example, a solution to the problem is an assignment of a value to each variable, from its respective domain, that satisfies all of the defined constraints. CSPs are useful in a variety of applications, including artificial intelligence, robotic control, test-case generation for software and hardware systems, medical diagnosis, resource allocation, crew scheduling, etc.
An important aspect of the CSP framework in solving complex problems is that the variables and constraints can be defined by multiple people, without requiring each person to be aware of all of the variables and constraints defined by others. In particular, this means that variables and constraints can relate to very different aspects of a complex problem, and may be defined by experts who are intimately familiar with the specifics of each aspect.
For the purpose of this disclosure, an expert is a human user (e.g., a CSP modeler) familiar with structural relationships between the variables and constraints defining the CSP and reasons why assignment of a certain value to a variable may contradict (i.e., not satisfy) a constraint. The expert is distinguishable from another human user (e.g., an end user) who may use the system to find a solution to the CSP.
For example consider the purchase-order of a new car from a manufacturing plant. Possible constraints related to the execution process of the order may be specified by different departments: (1) the manufacturing department may set a constraint such as ‘no metallic color is available in the next three months’; (2) the customer's relation department may set another constraint such as ‘car must be delivered to VIP customers within one month’; and (3) the sales department may set a constraint such as ‘the customer ordered a metallic-colored car’.
Accordingly, a complex problem can be divided amongst a group of experts for the purpose of defining the constraints for specific and exclusive aspects of a complex CSP. A complex CSP can be solved by a computing system referred to as the CSP solver. A CSP solver can be implemented in form of a software program executed over a hardware environment. There are several classes of CSP solvers. One of them is the ‘maintain arc-consistency’ (MAC) class.
In the MAC approach, the solver examines each constraint independently, and reduces the set of possible values that the variables may accept according to the examined constraint. This process is repeated for all constraints until a solution is found, or until the solver determines that it cannot solve the problem.
When a solver is searching for a solution, constraints originating from the different aspects of the problem, as well as those introduced by different groups of experts, are all considered together on an equal basis without any evaluation of the context in which each constraint is defined. Thus, one problem associated with the MAC process, and CSP solvers in general, is that meaningful relationships between constraints and variables (e.g., particular or relative importance of a given constraint within the context of the problem) are not considered by the solver when generating failure results.
Consequently, when the solver fails to find a solution to a problem, it cannot explicitly specify what aspect of the problem needs to be modified in order for the problem to be solved. For example, consider a CSP that is defined as follows:
                    VARIABLES        ⁢                  :                                              A          ⁢                                    :                          ⁡                          [                              1                ,                6                            ]                                      ;                  B          ⁢                                    :                          ⁡                          [                              1                ,                1000                            ]                                      ;                  C          ⁢                                    :                          ⁡                          [                              1                ,                4                            ]                                                              CONSTRAINTS        ⁢                  :                                              IF          ⁢                                          ⁢                      (                          A              =                                                1                  ⁢                                                                          ⁢                  OR                  ⁢                                                                          ⁢                  A                                >=                5                                      )                          ⁢                                                                                                            THEN            ⁢                                                  ⁢            B                    >=          180                ⁢                                                                                                IF          ⁢                                          ⁢                      (                          C              <=              2                        )                    ⁢                                          ⁢          THEN          ⁢                                          ⁢          B                <=        30                                                            C        =        2                                                            A        =                              5            ⁢                                                  ⁢            OR            ⁢                                                  ⁢            A                    =          6                    
Upon failure, a trace outputted by a MAC solver may look like the following:                Consistency: constraint 1: A=[1-6], B=[1-1000], C=[1-4]        Consistency: constraint 2: A=[1-6], B=[1-1000], C=[1-4]        Consistency: constraint 3: A={1-6}, B=[1-1000], C=2        Consistency: constraint 4: A={5, 6}, B=[1-1000], C=2        Consistency: constraint 1: A={5, 6}, B=[180-1000], C=2        Consistency: constraint 2: A={5, 6}, B=[180-1000], C=NULL        FAIL        
The above detailed trace of the solution process is difficult to analyze, and a user reviewing such result may not be able to understand the cause of failure. This difficulty arises because the trace provides information about multiple constraints in the system and does not semantically distinguish between them. Specifically, the above trace data will not aid users who are only familiar with certain aspects of a problem (i.e., those who do not know how all of the constraints and variables relate to each other).
Thus, methods and systems are needed that can overcome the aforementioned shortcomings by providing explanations for a failure result within the context of the defined constraints and variables.